{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q-learning (3 points)\n",
    "\n",
    "This notebook will guide you through implementation of vanilla Q-learning algorithm.\n",
    "\n",
    "You need to implement QLearningAgent (follow instructions for each method) and use it on a number of tests below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# In google collab, uncomment this:\n",
    "# !wget https://bit.ly/2FMJP5K -q -O setup.py\n",
    "# !bash setup.py 2>&1 1>stdout.log | tee stderr.log\n",
    "\n",
    "# This code creates a virtual display to draw game images on.\n",
    "# If you are running locally, just ignore it\n",
    "import os\n",
    "if type(os.environ.get(\"DISPLAY\")) is not str or len(os.environ.get(\"DISPLAY\")) == 0:\n",
    "    !bash ../xvfb start\n",
    "    os.environ['DISPLAY'] = ':1'\n",
    "\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "%load_ext autoreload\n",
    "%autoreload 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting qlearning.py\n"
     ]
    }
   ],
   "source": [
    "%%writefile qlearning.py\n",
    "from collections import defaultdict\n",
    "import random\n",
    "import math\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "class QLearningAgent:\n",
    "    def __init__(self, alpha, epsilon, discount, get_legal_actions):\n",
    "        \"\"\"\n",
    "        Q-Learning Agent\n",
    "        based on https://inst.eecs.berkeley.edu/~cs188/sp19/projects.html\n",
    "        Instance variables you have access to\n",
    "          - self.epsilon (exploration prob)\n",
    "          - self.alpha (learning rate)\n",
    "          - self.discount (discount rate aka gamma)\n",
    "\n",
    "        Functions you should use\n",
    "          - self.get_legal_actions(state) {state, hashable -> list of actions, each is hashable}\n",
    "            which returns legal actions for a state\n",
    "          - self.get_qvalue(state,action)\n",
    "            which returns Q(state,action)\n",
    "          - self.set_qvalue(state,action,value)\n",
    "            which sets Q(state,action) := value\n",
    "        !!!Important!!!\n",
    "        Note: please avoid using self._qValues directly. \n",
    "            There's a special self.get_qvalue/set_qvalue for that.\n",
    "        \"\"\"\n",
    "\n",
    "        self.get_legal_actions = get_legal_actions\n",
    "        self._qvalues = defaultdict(lambda: defaultdict(lambda: 0))\n",
    "        self.alpha = alpha\n",
    "        self.epsilon = epsilon\n",
    "        self.discount = discount\n",
    "\n",
    "    def get_qvalue(self, state, action):\n",
    "        \"\"\" Returns Q(state,action) \"\"\"\n",
    "        return self._qvalues[state][action]\n",
    "\n",
    "    def set_qvalue(self, state, action, value):\n",
    "        \"\"\" Sets the Qvalue for [state,action] to the given value \"\"\"\n",
    "        self._qvalues[state][action] = value\n",
    "\n",
    "    #---------------------START OF YOUR CODE---------------------#\n",
    "\n",
    "    def get_value(self, state):\n",
    "        \"\"\"\n",
    "        Compute your agent's estimate of V(s) using current q-values\n",
    "        V(s) = max_over_action Q(state,action) over possible actions.\n",
    "        Note: please take into account that q-values can be negative.\n",
    "        \"\"\"\n",
    "        possible_actions = self.get_legal_actions(state)\n",
    "\n",
    "        # If there are no legal actions, return 0.0\n",
    "        if len(possible_actions) == 0:\n",
    "            return 0.0\n",
    "\n",
    "        <YOUR CODE HERE >\n",
    "\n",
    "        return value\n",
    "\n",
    "    def update(self, state, action, reward, next_state):\n",
    "        \"\"\"\n",
    "        You should do your Q-Value update here:\n",
    "           Q(s,a) := (1 - alpha) * Q(s,a) + alpha * (r + gamma * V(s'))\n",
    "        \"\"\"\n",
    "\n",
    "        # agent parameters\n",
    "        gamma = self.discount\n",
    "        learning_rate = self.alpha\n",
    "\n",
    "        <YOUR CODE HERE >\n",
    "\n",
    "        self.set_qvalue(state, action, < YOUR_QVALUE > )\n",
    "\n",
    "    def get_best_action(self, state):\n",
    "        \"\"\"\n",
    "        Compute the best action to take in a state (using current q-values). \n",
    "        \"\"\"\n",
    "        possible_actions = self.get_legal_actions(state)\n",
    "\n",
    "        # If there are no legal actions, return None\n",
    "        if len(possible_actions) == 0:\n",
    "            return None\n",
    "\n",
    "        <YOUR CODE HERE >\n",
    "\n",
    "        return best_action\n",
    "\n",
    "    def get_action(self, state):\n",
    "        \"\"\"\n",
    "        Compute the action to take in the current state, including exploration.  \n",
    "        With probability self.epsilon, we should take a random action.\n",
    "            otherwise - the best policy action (self.get_best_action).\n",
    "\n",
    "        Note: To pick randomly from a list, use random.choice(list). \n",
    "              To pick True or False with a given probablity, generate uniform number in [0, 1]\n",
    "              and compare it with your probability\n",
    "        \"\"\"\n",
    "\n",
    "        # Pick Action\n",
    "        possible_actions = self.get_legal_actions(state)\n",
    "        action = None\n",
    "\n",
    "        # If there are no legal actions, return None\n",
    "        if len(possible_actions) == 0:\n",
    "            return None\n",
    "\n",
    "        # agent parameters:\n",
    "        epsilon = self.epsilon\n",
    "\n",
    "        <YOUR CODE HERE >\n",
    "\n",
    "        return chosen_action"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Try it on taxi\n",
    "\n",
    "Here we use the qlearning agent on taxi env from openai gym.\n",
    "You will need to insert a few agent functions here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gym\n",
    "env = gym.make(\"Taxi-v2\")\n",
    "\n",
    "n_actions = env.action_space.n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qlearning import QLearningAgent\n",
    "\n",
    "agent = QLearningAgent(alpha=0.5, epsilon=0.25, discount=0.99,\n",
    "                       get_legal_actions=lambda s: range(n_actions))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def play_and_train(env, agent, t_max=10**4):\n",
    "    \"\"\"\n",
    "    This function should \n",
    "    - run a full game, actions given by agent's e-greedy policy\n",
    "    - train agent using agent.update(...) whenever it is possible\n",
    "    - return total reward\n",
    "    \"\"\"\n",
    "    total_reward = 0.0\n",
    "    s = env.reset()\n",
    "\n",
    "    for t in range(t_max):\n",
    "        # get agent to pick action given state s.\n",
    "        a = <YOUR CODE >\n",
    "\n",
    "        next_s, r, done, _ = env.step(a)\n",
    "\n",
    "        # train (update) agent for state s\n",
    "        <YOUR CODE HERE >\n",
    "\n",
    "        s = next_s\n",
    "        total_reward += r\n",
    "        if done:\n",
    "            break\n",
    "\n",
    "    return total_reward"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "eps = 2.9191091959171894e-05 mean reward = 8.5\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAD8CAYAAAB6paOMAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xl8VOW9+PHPdyZ7SEggAULCEnYBATECCm6IiqilttVi\nN6uttF6senu7aK1bra1X29r23ra3/HrpqkVra6HqFZe63HqrAi4IKBoBZZNFNoFAtuf3x5yZnDlz\nziyZmUyS832/XiEzzzlz5pnD5PmeZz1ijEEppZR/BXKdAaWUUrmlgUAppXxOA4FSSvmcBgKllPI5\nDQRKKeVzGgiUUsrnNBAopZTPaSBQSimf00CglFI+l5frDCSjqqrKDB8+PNfZUEqpHmX16tV7jDHV\nifbrEYFg+PDhrFq1KtfZUEqpHkVE3k1mP20aUkopn9NAoJRSPqeBQCmlfE4DgVJK+ZwGAqWU8jkN\nBEop5XMaCJRSyuc0EOTQ/iPNrukHmlrI9i1E29sNB460xKQfPNpCa1t7Ssd6esMuXtuyH4C9h5sT\n5v1AU+rvEbbs1W2e581LW7vh/pXv0dzq/Z7t7Ya9h72Pa4xh057DHG1p4/6V79HWHv0ZDx1rjfpM\nbR7n183RljYONCXed58tf/GOv/9Ic1T+jrUmd/xkGBP/PPVWL23ay/rtBzN6zO50HoO33nprrvOQ\n0OLFi29duHBhrrORlL2Hm8kLCsGAxN3v9a0HOP3uZ6ivKuX3/3yXxl2HeGf3IYryg5xy598pyAsw\nrb6f5+v3HW4mGBA+OHyMYEA4fKyNovwgza3tfHi0haL8YMxrdn94jMfXv0//PgUseX4zl/36JT46\npZYDTS1s3dfEl/6wmluWrWPzB0c47/iayOfZ9eFR9h9pYeXmfYys7hM5XmtbO+t3HOSTv3yB59/Z\nw4WTBtPw3Sd5cPVWpg6tYNu+Jh5f9z63Pbye4f1Lqassobm1nQm3rOCnf2/kcycPJxAIFWoHm1op\nLghy29/WsWVfE5PrKmhpa2ffkWZKCkLzHt98/yCf+dVL/NezGzllZBWDK4rY9eEx+hTmcehYK/e9\n+C7Dq0r55bMbqS4rpF9pAQCPrNnBVx94jT+88C6XnTyc5xv3cNOytZw7YRAFeaFroZuXrWPRfS/T\nv08h//2/m8gLBtiy9wiHm1s5557n2LKvia/96TV+9Y+NPLZ2J2WFeZQUBHn5vX2MrC5l3k/+l7se\n28Bzb+/m+Lq+3Pa39Xz1gdf40mkjeWDVFuoqS1i7/QDrtx+kf2kBV/5uFd/88xpOGFrBRT97nhXr\n3uczM4ZhjGH7gaMUBAMcPBo6J8da23h2w27m/fQfjBlYxuiBZdz40Ossuu8VhlSW8NrW/Rw3qIyD\nR1v4wwvv8qlfvUhLWzuzRlUBcOLtT7L4uY384+09zB43gOKC2O/Gk+t38oPHNzDv+BpEor+7Hxw6\nRlu7Yf+RFpa/toNLfvlPThlZxR2PrqdPUT7D+5cCoYB240NreW3LfqYOqyQvGDq3T6zfydZ9TTyy\nZgfVZYVUlhS4fqf3H2nmxofWcqy1nZuWrWXFup1MquvL55a8xB9feo/KkgIadx1i58HQ+bnityuZ\nVt+PCtvxnn1rN9v3NQHwxd+u5JX39nO0pY1New5TXVbIe3uPsOi+l5lY25fyovyov9OjLW3sb2qh\npCCPJ9fv5FhrO9VlhbS2tXPqXU9z74vvcd2cMTH5PnSslaaWtpi/uW37m9h54CgvbtrL6IFlvPvB\nYf76yjaOG1zOmzs+5PS7n6GsKJ+avkX0KczjrhUbWLN1Pw3DKjl0rJVDR1u5+r5XqOlbTG1lses5\nS+S2227bceutty5OtJ/k6ub1IjIX+AkQBH5ljLnTa9+GhgbTE2YWt7a1M+rG/+FjU2v50SVT4u77\nwMotfOPPa/jEiXU8uHprJH14/xI2f3CEyUMqWLZoZtRr1m47wJd+v5pHrpnFlO88gQjY//vu/sQk\nvv7gGgCe+/qZ3P34BnYePMovP3MilaUFXPxf/8fKzfuS+iz/fVkDs8cNoP6GR6PSH/7KLPqVFvDo\n6zv49fOb2ba/KbJtaL8S3tt7xPOYb333PKbe/gSHjrVG0maNqqJvST6PrNnBiKpSNu45DMCm78/j\ntr+t5zf/t5njaspZdOZIrr7vFdfjnjammpHVpfz6+c1R6X9dNJPJdX15cPXWyHkpLQhyuLktss/k\nIRVcd9ZoLv/NyqTOi5uvnTOGHzz+VqdfH/bM187g/lVb+MUz71BXWczWfU388OLJ3LRsLUesPF8+\nczhNzW0sXbkl6rUVJfnst9UQBpYX8pXZoynIC/AN67OH3XrheF7dsp/SwjzuffG9qG0fO6GWHQeO\nsm1/E/VVpTz71m7XvI4a0IfGXYciz+urSmkYVsmfrO/y7fMn8PNn3mHHgaMxr3391nP48ZNv06cw\njylDKrjyd6sYV1NGVZ9Cntng/n5eRlSXcr4VvD46ZTCzf/hsSq8HeOhfTuH3L7zLX17eFpVenB/k\njdvncu3SV1j26nYAvjN/Au8fOMrPn3kHgBkj+vHCxr2R19z2kQlMq+/H6nf38e2/ro2k1/QtipyL\n2opiFp42gluWr3PNz6xRVfyjcU/kecOwSh686pSUPxeAiKw2xjQk3C8XgUBEgsBbwNnAVmAlcKkx\nZr3b/j0lEBxtaWPcTY9REAzw1h3nxd33T6u28PUH1/DxqXX8+eWOQBC+up0ypIK/LprJCxs/oLm1\nndPGVLPwd6t4fP1O7vnkZP71/tfiHj98HICfLJjCpLoKzvzBMyl9nrLCPD60Fdrp+smCKVy79NWk\n9v3irHqWv7adXR8eS+s9zz++hqL8YNQ5dgoH30wpK8rjw6OZO2+9jf272d2VFAQjQThXZo8bwJLP\nn9Sp1yYbCHLVRzANaDTGbDTGNANLgfk5ykvGtFhtxIbEwTVgVb8TBeIFi1/gc0teso4bcrAp8R+R\n/Q9t1eZ9KQcBoFNBYGJtuee22x9+I+nj/Oofm9IOAgCPvL4jbhAAMhoEivODrLnlnIT7/fHKGfzx\nyhkcV1OOxG9FBGD0gD6u6dfMHsWiM0emmk0ATh1dxckj+jNlSAVLPt/AhMEd/3f//vHjqa8q7dRx\n7c4cW83rt57Dt+aN46YLxgOh7+b0+n6MHtCHYpcmzPE15bz4rbOYPKQi7rEvnDyYM8dWc8rI/pG0\ny2cOj9pnzMA+nDC0gu9ddHwk7aYLxvOxE2pjjve9i47n5ZvOpmFYJWWFoebII81tDCwvTPg5ne8L\ncMbYamaM6GjevWBSTdT22oro5p5LGupYunAGk+v6RtLqOtkklKpcLTpXC9jrtluB6TnKS8a0toWK\n6pY2w/DrH+GfN8ympm/0f+TrWw/w6tb9lFrttO0egSBe4eDV8VeQF3DtEF2/I71OrmvOGs1Pn3o7\n4X5fOm0EE2v78pU/RjfhjK8pp3H3IfYcil+wf/v84/juI/GDxf0LZ9DabqivKuW1Lfu56t6XI9um\n1/fjxU17PV+75PMNXPGbVZQX5XH7RydG1U4qS/LZl6Bz97MzhjF9RD+u//Prnle0hfmBqDb2Td+f\nF9O8lhcQTrYKr/+59lQAhl//CAAbvjuXsd9+DIBLpw2lvDiPf7y9hx9dMoVzf/xczPt99ZyxGGNo\nam5nyfOborb9/gvT+MvL23jolW2cOrqKX13WwE+fepufPf2OtT36T272uIFs2XuEf77zAZecNIRP\nnjQUCF2sfPkPq1mxbicDygp57LrT+I+/v83Rlna+fu5YdhxoYsP7H/LVB0K11L9dPYtvPfQ6P//0\nVIb0KwFg4WmhYLVtXxPVZYVcdUZH8Nq+v4kjza3M+dFz/MsZI/nG3HEALFs0k0fW7ODN9w/yH39v\nBOCx605l7o//F4BvnDs2cvwte49QV1mMiHD5KfWcdvfT3HzBeK6YVQ+E+qEm1fVlzMCySL/Qjz45\nhXtffJff//NdfnDxZCbWhgrgB686hWOtbdz34ntMHVrJ5CEVbNvfxD1PvBVpxr2koY6avsX8xPq7\nuOXCCYyvKWfb/iZOG1PNgLJC6ipDeTva0sYfXniXz8wYxs0XjOefGz+gX2kBJw3v59qXt+zqWew5\ndIzH1r7Pp6cPjemzyYZcBQK3TxZVIorIQmAhwNChQ7siT2lrdYwkeXHjXi6cPJiT7niSa2aP4vMz\n67nwP/8BwI8/GepDaPOoELidoHCaVyAo9AgEqY6ysZtc15fyosRfk79dPYuJteWsWLczZtvR1jb6\nFuez27rCX/zZE1n4+9Ux+10xs57igiBNzW2eAWH6iI6rv0HlRVHbBljPvzirnqtnj+KOR96ItFkD\n1FeFrqo/M2MYZx03kNPHVFOYF+Dx9Tupqyxh35EDAAzpV8yWvaG+j3BbPcDxdX25YNJglr60hX80\n7onp36nqU8jPPz0VgKULZ9CnMC/qj/jcCQNZsW5nJAjYPXbdqew6eIzCvCBXzKxnyfObuGBSDTNH\nVYGjlfH8STU8smYHw/qHChoR4YZ543hv72E+d/Jwxgws4+kNu5g1qoqThvfjpOH9WHDSEAIB4cpT\nR0QCgZsh/UoihWuYiHDVGaNYsW4nJQVB+pUWcMuFEyLb+5UWMGFwX17atJczxg7g+Lq+/O0rs1yP\nf/OF42PSBltXxqu/PSeq4zf8Wc+fVMOrW/bzv2/vYdygcjbfeb5rvsOG9i9h1bfn0M92rGBAIgW9\n3aenD+PT04fFpBfmBbl8Zn3keW1FMbfPn8ieQ8cYWd2Ha2aPpm9JPiUFwcjf/cUNQ1w/c1F+kC+e\nOiLyeP6U2NqIU1WfQj4zIzZf2ZKrQLAVsJ+1OmC7fQdjzGJgMYT6CLoua53X4jIk8rWt+9l7uJk7\nH3uTz9u+WOHhfU2O9sdkYv9Bj0DQ3u5+mtIZOtjSZih0uWpxqq8uRUQoyIv9BEeb2ygryosEgnMm\nDGJkdSnv7D4ctV8gIHx6+jD+tGpLzDGG9S+J/DHZ93/ma2dwhtXsFa5lVZYWUFFSwN0XT+bG849j\nyneeCOWxqpRXbjqbSms00W+vmMbKzXt5fP3OqNEjf77qFJ7dsJuyonxOGFrB9O89BYSu5AH+/ROT\nuOmva7lx3nFRgeChfzklUiDNsAWs//e5Bh5YtYX//NRUnli/k5NHxAaCcYPKGTco9PjmC8dzzVmj\nYgrF7110PN966HXmThjEDy+eHFVrzA8G+NVlHe3Il04LXTwV5Qf51PSOC6m+xflAqB8jFeGLAefF\njt2dH5+U0jGd+vfxboJZ8vmT4g7/daqKc6zOKi4I8pvLp0Wlfen0zjXLdTe5CgQrgdEiUg9sAxYA\nn8pRXjLiK398hb+9tj0mPVwIlxXlR6UfaQkFgKYWRxNDnEgQ/hN0CzhA1GgYuz2HOl8jaG1vj2rH\nDQjYy4IfXDyZl9/bFymE84Ox3U4jB/SJ6Tw9fcwA3tm9KWZfIDK88ZzxA3l8faiG8ezXz3Tdd7it\nHTvcymYv1EsLo7/i4SAQNswquBecNIRXrbkQA8qKoq7uqvoUsOdQc+S4tRXFrp13btV8gLPHD+Ts\n8QMBmHd8jes+Ts4gAPCp6UO56IRa1+GfyRIR/njlDIb2L0m8s034+zt2YFmn3zsd+cGA63dLZUZO\nzqwxphW4GlgBvAE8YIxxH0vVQ7gFgdDwzlDp5LyKP2K1MTtHJCRTI/BqTsqkcOfke3uPUJjX8TVx\n/jGePLI/37vo+EgTiHP7jBH9+M9Lp9KnMPlrjnBHeiDJttGffWoqN1/Q0eQQtL0uUeExoLyIxjvO\nY8E07+bHR645lY9NreXcCYNitl06rSNgpFNAJysT73HyyP4xHZWJVJcV8ocvTOeeBfGHRaueKWd3\nKDPGPAo8mnDHHi58lXrMUa0NX707m4bCRIQn1se2twO0tXduVm4qJtVV8PauQ1x1+iiONHdczecF\nBHuXr3PUR0FedME757iB9C3JjzRj3OLSRgyhK/KwcAd6IADf/9jxVBTnu74m7HxrNMY3rfHybpP5\nKku8j5GXIFgMLC/ynBfy/Y9N4o8vhZqyivJ69xXrrNFVuc6CypIecavKnsyrSbWp2b1GEPb+gaNc\n+buOuRONuw5FAoNzeYN4+pUWJJzKPrC8kHGDyqMmDxXkSaRT7rf/t9nztUX50YVfgaNQ7esoxMOF\ntP1i/8mvns4o2/DI8McTkUhbdyrygtGBYMV1p9G/j/ts1kxKFFCU6q70m+viQFMLR1syM4nEa55A\nuEZgv9oGIk0s2w80RaXP+VHHjMlUlulxjqxxzyPcPn+iaz4ALvEYDQGh0RV2zqaYcCAIH8/tat0Z\nPE4aXgnAZ1xGc8QTnr/hfI+xg8qS6jw8bUw1p49JeJ/vGP86Z0xk3LlSPZF+e11Mvu1xJtaW8/BX\nTo27344DTQwoK4q7rpDXxXub1dB/+Jh7wIk3z8xr7oGbkiTalIMBibmKzrN9puKCIDfOO447Hu0Y\n0tkwrJILJtXEfPZ8x3HCV+Lh1DyXc5XvGGlU07fYdYhgsoKdHHf9uyumJd7JxbVzRnPtnNGdeq1S\n3YHWCDys3RZ/EtauD49y8vf/zl2PvRl3P68aQZuV3uSoeSRThnmNGnJTaGu6+eiUwa77BCQ2EDhH\n2ziNGtAnajhsWF4g+is1dWhlzHtB9PBF52uUUl1L/wI7ac+HoXZ3r0W5wryu3VNp53dydjzHY2+6\nuf2jE133CQaEfEdhXOLoBE5m2QyAFltH9rD+JZEmoXCACwecL9vGXzubhpRSXUv/Ajth857D/OiJ\n0GqTiaZ/25txnOvVu0mmUSOVQGDvzPUajpkXEPIdI15KEtQIvD52XWWxa3t5ePegFXDsY+6dTUPp\n6oIZ+Ur1KhoIOuHXz2/iyTdCI3gS3HYgqo/gWw+9Hnns1byTzLoiLSkEAnvh7xUIAgGJabtPpm/B\nTWFeMLK8gL1VLNJZ7JIHnSikVG7pX2CSDh5ticw8LbcNiYw36amt3UT1ETywqmM5glTa+Z2aO/la\nr6wGJLYwPn+S+wzYzjZoddQIYjPh1oGslOo6GgiSdOVvV/HRnz3Psda2yB2zIH6NIBQI3Ld5Ne8k\n1zTUuaGtXoHAmFABHa4F3P7RiZQ7lsQIf44Th4U6f8NLJrgJH2fMwNilk93OV6ZWV8zRPZaU6vE0\nECTpta2h2kBbu8F+8RyvEGtrN56drKksoJXqa+falkKw5088wky4H+NUa+ZovGL5uJpy3vnePGaP\n8w4EA8qLQssRfLJjNm5Xttt7fU6llDsNBEkKFy7GONu+vV/T2m7wWg0inaahljiLDVWU5PNfnz3R\ndZtX7cV5tHjNXcaYhPdjhtByBNEL7WnhrFR3pRPKkhQu+wzRBWe8QrPdGM/JX17t/MlcOXstGWFf\nSuGa2aP4qXUzjx9cPJnKknzvvDqy6LZbuA+hsx27Yjt/YdVlhZGlqZVSuaOBIEnhJpZ2E93uH+/i\nuLXNYDzWOkunacjL2EEdSwSPtNbuEeATJ9YB3pPbwqnhWo/bR/rU9KG8f/Aoi84c1am8hY9pz8Lj\n153GvjRumuOkXQRKdY4GgiSFC7J2R7t/wj4Cj8L3rZ2HMpm9pHjl1Vlrcas5FOUH+da84zKQi473\nqiwtiLk/QEZoK5RSKfF9H0FTcxs/f6YxarKXK6twaXf0EcStEbQbz7WGMmFIv8zc2DomVmWhII00\nDXXFZbtWDZRKie8DwU+eepu7HtvAX17eFne/cNnonBGcqI8gmwXfY9eexjNfOyPuPsn0OThHNiV7\nQ5hU6Egepbov3weCw9adwo4mGJsfblYxJrq5J+6ooTbvzuJMKC3MY2CCZaaTeXvnyKZsFtnZvFj/\n8ukjGNa/hLOOG5DFd1Gq9/F9IEhWuAmoLaazOF4fQXuk4JtznPe4+7Ty5fE/mE78ycaY/65oGho1\noIxnv35m3JugK6ViaSBIUseooeir2nidxcda2yO1h+oy78Jpxoh+kcepFpSJmnGSahpKorM4Xd+c\nO46Zo/pzxtjUb/yilMouHTWUpKhRQ0l2Fh9pbqPd6lOIt55OdVlH884HCW4r6dTZm7DYxfQVZ6FG\nMLyqlHu/OCPzB1ZKpU1rBEmSyKih6OGjzqtnEbj3i9MpKQhy+FhrZM94s3HTWXPNe45Y8lWLcGDT\n5ZuV8icNBHEse3VbZCmIcBOQcyE5t0J85qgqhlSWcLi5NTJ8NF4gSKf8TbRgWzLHdt4PIBtNQ0qp\n7sv3TUPxrpyvXfoqm/cc4do5ozuahoyzKcW90CwpDHKkuS3S/h43EOSo4B3Sr5iPTqnlohNqHfnJ\nSXaUUjni+0CQyM4PjwLRTUP2KoGzfA8/7VOYF2oaSqZG0ImC94cXT467PZlOZ0H4t3PGuqYrpfwj\nraYhEblYRNaJSLuINDi23SAijSKyQUTOtaXPtdIaReT6dN6/K0Taz+lYa8jOqxmlpCBUIwjvH69T\ntzMF78et9YO8hO9VnOgm9K750TiglK+kWyNYC3wM+KU9UUTGAwuACcBg4EkRGWNt/hlwNrAVWCki\ny40x69PMRxaFCvJw4fj0m7t5cdPeyFYR+P0/N8e8qig/SFNLW1KdxdkoeOdOHMTXzx3LZacMT/m1\neoMXpfwlrUBgjHkDXNu45wNLjTHHgE0i0ghMs7Y1GmM2Wq9bau3bbQNBR40g5N8fezNq+weHmrlp\n2brI8/C5CIhgTEcNwh4IAhJ9L+NURg39ddFM9h5OvHRzMCCdXilUKeUv2eojqAVesD3faqUBbHGk\nT3c7gIgsBBYCDB06NAtZTE7H0EqP0torWaJHGNkDQV4wELUMdSpNQ1OGVMSknTG2OuquZEoplYqE\ngUBEngTcSpkbjTHLvF7mkmZw75NwbYgwxiwGFgM0NDTkrLEifEXvFQfyg+4bQjUC4zpqKC8g2KeN\neS0TkazfXD4t8U5J0L4BpfwpYSAwxszpxHG3AkNsz+uA7dZjr/RuzauQ9OosDorQbjqagOydxbGz\njLtHCax9A0r5U7YmlC0HFohIoYjUA6OBl4CVwGgRqReRAkIdysuzlIeMcN69yylmZnE4PRC9DLWz\naSjqNTmKA1oDUEpBmn0EInIR8B9ANfCIiLxqjDnXGLNORB4g1AncCiwyxrRZr7kaWAEEgSXGmHUe\nh+8WEi2/4LXMtERqBO5NQ3bpLDGhlFLpSnfU0EPAQx7b7gDucEl/FHg0nfdNV1NzG4V5AQJJlMDh\nmcdeezpvVBMWkOh7FwTiBAKdwKWUyiXfrTXU3m447ubHuGnZ2uReYJXzXn0BzhpBeLeAiLVAXSgo\n2Mt+Z9NQQKAgL/f/FdpUpJQ/5b706WKt1hX8/Su3JNizQ0tbO/uOuC8P7V0j6GgaEpGoq/6YGoEI\nj15zatL5UUqpTPJdIAhL9urXAN/88xr2HWlJ+fjt1s3rY2sEsW8+akCflI6vlFKZ4rtA4FxtNFH7\nvDGGR9bs8NxeV1nierxI05AJXfHbA08w4Gwa6l5tMqncy0Ap1fP5LxA4FpFLuD9QXBB03ZYfFJ59\na7frtmAg1DRkjIl5p9imoaSyknHdK/wopXLFv8tQJ1kKthsoygsCsU1DgrDX49aSIqH+gV8+tzFy\nnDBn01CuCmS97ldKgY9rBKnwqhHEK8HDTUNh9sfOJamTGcaqlFLZ4r9AkGBeQMz+xlDYiaGdAYGW\nNnsg6NjmXJJaw4BSKpd8FwjaE8wUdjJ430sg3iGcHcDGXiNwGT7aHejENqX8yXeBIFwgJ13oGe+5\nAq7lt4S3OQNBx+PYQJBcVuoqi5PbUSmlUuC7zuJUuwgMxjsQuASTyKJzjk3tLjWCYEBoa48dVeTm\nD1+YzqzRVclkWSmlUuLDGkHod/gq/O9v7kq4f0o1Akts01DH43BncTggJFMjyEbrkdchdTlqpfzF\nh4EgurN42/4m1+12rZ41Am/O5h97jSDcbBTvhvapvJdSSqXDh4Egte3xagTxOMt4+3HDE8rCv5O6\nAtdIoJTKEv8FAut3siN14vYRuBzDvvqonVsfQXj+QHJxQCOBUio7/BcIbAWyWzOQM6XddK5pKLaz\n2PY6a1swhRpBpvoILmmoY2JteWYOppTqFXwXCCLzCHBv8nEGB2PcA0bkIB5iOouJ7SMIB4tkFnnL\nVH3grk9M5raPTMzumyilehTfBYJIoSvRV+nxX+MuXrkZbx6BOPdJqkaQuVI6fKjuMpFNKZVbvgsE\n9kLX7X7DyaSExStIw1f7NX2LeOM7c2lvt9cIQr/Do4a6erSmFv9KKTvfBYJIZzHJjQaK135vjwO3\nXjjeOm7H/QggtNJocUEwqrAPb4tUCLp44L7WBJRSdr6bWRyuBYgIbW41Aufw0SSP61yhNDwiKBwY\nouYRhPeR5DuLM8krDNxywXiK8oKcPX5gl+ZHKZVbvgsE9kLXtLtsx9lZbDyv2O0FqvMq3zlqaIj9\nTmbhfXJUH/OqEAwoL+KHl0zu2swopXLOv01DgmuNwOnpDbs971dsb2JxjhJyBoaPTa2N2RZIoY8g\nk81HOidBKWWXViAQkbtF5E0RWSMiD4lIhW3bDSLSKCIbRORcW/pcK61RRK5P5/07w77EhPvw0eSP\nZS9OnUtKOGsE0UHDek2umoY0DiilbNKtETwBTDTGTALeAm4AEJHxwAJgAjAX+LmIBEUkCPwMOA8Y\nD1xq7dtlOhadE9dRQ6mwF6jOu4yFC3576rhBZaF9nZ3FObpppMYDpRSkGQiMMY8bY1qtpy8Addbj\n+cBSY8wxY8wmoBGYZv00GmM2GmOagaXWvl3GJBg+mpqOojTm9pORwr4j/cGrTuH/rp8dSQu/e3Iz\nizM/j0AppSCzfQRXAP9jPa4Ftti2bbXSvNK7jP3q2940dPOydaHtnYwN4QqB1/0IAPoU5jG4orhj\nW46We9Y+AqWUXcJRQyLyJDDIZdONxphl1j43Aq3AveGXuexvcA88rsWhiCwEFgIMHTo0UTaTFmka\nAtqTGDUUj1vTUGSJ6Tg3pA8GnDWCrp5H0KVvp5Tq5hIGAmPMnHjbReQy4ALgLNNRom0Fhth2qwO2\nW4+90p0tgaflAAAT/klEQVTvuxhYDNDQ0JCxkrJjHkFyo4bicRs+Gtnm0kfg3Dd8urp8ZnHyK1so\npXwg3VFDc4FvAh8xxhyxbVoOLBCRQhGpB0YDLwErgdEiUi8iBYQ6lJenk4dU2ad1uS4xkcqoIVsp\n7yzw41QIYgrirh415AxaSil/S3dC2X8ChcAT1hXwC8aYLxtj1onIA8B6Qk1Gi4wxbQAicjWwAggC\nS4wx69LMQ0qiOos7ccMZO3tbu7NsjRS2LmVuuGO5PVIj6OKmoS59N6VUd5dWIDDGjIqz7Q7gDpf0\nR4FH03nf9MRvGkqlSHa7sHZ2Frs2DTnuQ5CreQQaEJRS4MOZxe2JOos7WSoX5IVO5ZShoTl1ziGi\ndh2LzeG5j9drMkNDgFKqg6/XGkp7QpntcUlBkOVXz2REdR+gIzC4NT8FnZ3FOrNYKZVD/gsE9qYh\ntyUmUjqWnTCpLrLCBoXBUCBoaYs9YiDSR5DCmymlVJb4rmmoYx5BcstQJ3MsiB0lVJgfOrWtLu1P\nsbeo1IiglMod3wUC+zyCdCdyRd1jwNHeUhAM3Z+g1a1G4OgsduurUEqpruK7QGAv+9vcCuBUagS2\nx141ghaXN/FqGiorCrXUDelXTFWfguQzkqKu7pNQSnVvvgsEdsncqjIee43CuX5PgdVH4PYeHUEj\neh7BPZdMAaCiuIDyovy08pYU7TRWSuHDQBC11pDrPILkg4O9jHeOxAmPGmpxCwQe8wjijebRMlsp\nlS2+CwT2exanu8REvD6GQisQtMZtGopea0iHdSqlcsF3gcBedKfbNBTv5ZF5BC77dIwasn479tGA\noJTqSv4LBLZS171pyN1dH5/EwtNGRKXFW6uoMC/ouS1SI2iP7iNwu0+ABgWlVLb5LxBYv0MTyly2\nezT3BAMSUyjHm5mcH/QuwWNuWh/JVOy+GgeUUtnmv0Bgm0eQyhITbjeaiXc/g/C8gmvOGh2zzXmH\nMtc4YD25fGY9QGTpiszQ8aNKqQ4+DATujyNpHq9za6JJ1Mew+c7z+erZY2LSzxg7AICLptZa+ejo\nwHZm5IJJNWy+83z6lWZ+XoHWNpRS4MdAYP0OtcdHF+TGGM9RQ8GAxLThd7azeXhVKZvvPJ8TrJVK\nnUexv0smb1qvlFJu/LfoXJwawbJXt1PVp9D1dXmBgEsfQXp5mTmqioJgINL849Y0pJRS2ea7QBC1\n1pBj23X3v+r5uuIC71FA0LllGwaUFfHWHedFnse70Y1SSmWL/5qGbDOLUym8i/ODkfsIZEu46cme\nLW0ZUkplm/8Cga2YTWU5ieL8oOvIoUzSQl8plQu+axoKl/0iklqNoCAQd25AJm9AH9VZnIXGoWH9\nS5k9bgDXugxtVUr5j+8Cgf2exW5Fd0EwQLPLTLOi/CDBgHcFKhNLO7sV+dmoJeQHAyz5/EmZP7BS\nqkfyb9OQx41pvDqFi/OD5GW5aUh7hpVSueC/QJDgyr0o3/2UFBd0QR+BRgKlVA6kFQhE5HYRWSMi\nr4rI4yIy2EoXEfmpiDRa26faXnOZiLxt/VyW7gdIlT0OuAUFr8XiivKC5CWxflA6XIePamxQSmVZ\nujWCu40xk4wxU4CHgZut9POA0dbPQuAXACLSD7gFmA5MA24Rkco085CSyHIOuHfwhu8j4BQICHke\nfQRnjK1mYm15xvJoL/21lqCUyra0AoEx5qDtaSkdF9zzgd+ZkBeAChGpAc4FnjDG7DXG7AOeAOam\nk4fU8xz67TVqqNClaeizM4YBePYRfO2csRlZCkKLfKVULqQ9akhE7gA+BxwAzrSSa4Ettt22Wmle\n6V2mY+1/96ah7fuPer7Gq48gU30HbsFEm4aUUtmWsEYgIk+KyFqXn/kAxpgbjTFDgHuBq8MvczmU\niZPu9r4LRWSViKzavXt3cp8mCVFrDbls33u42fM1Xn0EmRpNpH0ESqlcSFgjMMbMSfJY9wGPEOoD\n2AoMsW2rA7Zb6Wc40p/xeN/FwGKAhoaGjM3Wst8oPt49h6NeY/326iPI9GgiQZuJlFJdJ91RQ/ap\nqR8B3rQeLwc+Z40emgEcMMbsAFYA54hIpdVJfI6V1iWu+M1Kvvi7VaG8I0nPBQ7HC68C3ytApMp+\n9OjlspVSKnvS7SO4U0TGAu3Au8CXrfRHgXlAI3AEuBzAGLNXRG4HVlr7fccYszfNPCTt72/uik5I\nup4R2tFriYkMxQFtGlJK5URagcAY83GPdAMs8ti2BFiSzvt2xtGWtqjnoWWo40eCgeWF7Dx4rMtq\nBPY6gZb/Sqmu4puZxW53E0vURRB+SXg/r5vWZCwOuNCAoJTKNt8sOudW5idqGQoHgPDNbCbW9uW+\nL06nX58CSvLzOO3up4HQOkSZZG8O0qYhpVS2+ScQOC7/RYT9R1oSvcr2b8gpo6pi9irKcCBQSqmu\n5J9A4Hj+xo6DvLHjoOu+YbWVJew51Mz4mvjLR+QHM9s2lIklrZVSKln+CQSdKFxPGlbJ9y6amDAQ\nZIpbM5AGBaVUtvkmEHTmBmLtBiYM7pv5vHjQQl8plQu+GTXUmVtJTh1WkYWcJKadxUqpruSfQJBi\nHLj+vHFcMGlwdjKjlFLdiH8CQYr71/Qtyko+UqXNRUqpbPNNH0GyC8ylon9pgeuN7jMhE/c3UEqp\nZPgnEKS4fzIF8YvfOqszfdBxdBwtG4FLKaXc+CcQZKFczcvw/IEwrQsopbqSj/oIUosEuS6MtWlI\nKdVVfBMIUm3D0XJYKeUXvgkE2uKulFLu/BMIUq0R5KBxSPuHlVK54J9A0IPqBNo/oJTqSv4JBD20\nj6DnhC+lVE/ln0CQ4v7dJA4opVTW+ScQ9IAGeLccakBSSmWbbwJBqrRpSCnlF74JBKlXCLo+EojH\nY6WUyibfBIKeRmsCSqmu4ptA0FNHDXWTbCilerGMBAIR+ZqIGBGpsp6LiPxURBpFZI2ITLXte5mI\nvG39XJaJ909GT5hH4JbD7p9rpVRPl/bqoyIyBDgbeM+WfB4w2vqZDvwCmC4i/YBbgAZCZdxqEVlu\njNmXbj4SSX1mce5Ijt9fKeUvmagR3AN8g+iL1/nA70zIC0CFiNQA5wJPGGP2WoX/E8DcDOQhoWzc\njyCbtCaglOoqaQUCEfkIsM0Y85pjUy2wxfZ8q5XmlZ51PWEegVJK5ULCpiEReRIY5LLpRuBbwDlu\nL3NJM3HS3d53IbAQYOjQoYmymVBPm1mc6/dXSvlHwhqBMWaOMWai8wfYCNQDr4nIZqAOeFlEBhG6\n0h9iO0wdsD1Outv7LjbGNBhjGqqrqzvz2RzHS23/XLQM2fM4qG8RAAVZuguaUkqFdbqz2BjzOjAg\n/NwKBg3GmD0ishy4WkSWEuosPmCM2SEiK4DviUil9bJzgBs6nfvUctw1b5MBIvAfl57As2/tZnhV\naa6zo5Tq5bJ1z+JHgXlAI3AEuBzAGLNXRG4HVlr7fccYszdLeYjSE2oEdhUlBcyf0iXdJ0opn8tY\nIDDGDLc9NsAij/2WAEsy9b7JSr2PoOsjQXlx6L+jXmsBSqkulK0aQbfTEwYNjRtUzm8uP4kZI/rn\nOitKKR/xTyBI+e712clHImeMHZB4J6WUyiDfDEnpCTUCpZTKBQ0EHnQcv1LKL/wTCFJsGsr1EhNK\nKdVV/BMItGlIKaVc+SYQpErrA0opv/BNIOhpE8qUUqqr+CcQpNpHoHUCpZRP+CcQpFgjKC7wzalR\nSvmcb0q7VPuKi/KDWcmHUkp1N/4JBClWCYo1ECilfMI/gSDF/YsLNBAopfzBP4Eg1T4CrREopXzC\nN4Eg1TqB9hEopfzCN4Eg1RpBYZ5vTo1Syud8U9qlfGManVGmlPIJ/wSCFCLBKSP1xjBKKf/wUSBI\nPhLcd+WMLOZEKaW6F98Egqfe3JXrLCilVLfkm0Cw+LmNSe336elDs5wTpZTqXnwTCJJ1x0XH5zoL\nSinVpTQQKKWUz6UVCETkVhHZJiKvWj/zbNtuEJFGEdkgIufa0udaaY0icn0676+UUip9magR3GOM\nmWL9PAogIuOBBcAEYC7wcxEJikgQ+BlwHjAeuNTat8vcv1BHBCmllF1elo47H1hqjDkGbBKRRmCa\nta3RGLMRQESWWvuuz1I+YuhEMaWUipaJGsHVIrJGRJaISKWVVgtsse2z1UrzSu8yGgeUUipawkAg\nIk+KyFqXn/nAL4CRwBRgB/DD8MtcDmXipLu970IRWSUiq3bv3p3Uh0mGxgGllIqWsGnIGDMnmQOJ\nyP8DHraebgWG2DbXAdutx17pzvddDCwGaGhoSHWpoDj5zNSRlFKqd0h31FCN7elFwFrr8XJggYgU\nikg9MBp4CVgJjBaRehEpINShvDydPKROI4FSStml21l8l4hMIdS8sxn4EoAxZp2IPECoE7gVWGSM\naQMQkauBFUAQWGKMWZdmHlKiNQKllIqWViAwxnw2zrY7gDtc0h8FHk3nfdOhcUAppaL5bmaxDh9V\nSqlo/gsEuc6AUkp1M/4LBBoJlFIqiv8Cga1O8NS/nZ7DnCilVPfgv0BgqxGMrO6Tu4wopVQ34btA\noJRSKprvAoH2ESilVDRfBILGXR9GHouOG1JKqSi9PhDs/vAYc370XOS51giUUiparw8EHxw+FvVc\nA4FSSkXr9YFgw/sfJt5JKaV8rNcHgmuXvhr13GRsQWullOoden0gcNJAoJRS0Xp1IGhta49Ja9dI\noJRSUXp1INhzqDml/a88tT5LOVFKqe6rVweCQX2LePuO86LS4tUIbjx/fLazpJRS3U6vDgQA+cHo\nj6gtQ0opFS3dW1X2OO3G8IVZ9TTuOpTrrCilVLfgu0BggJsu0CYgpZQK6/VNQ05G24aUUiqKDwNB\nrnOglFLdi+8CQbsGAqWUiuLDQKCRQCml7HwRCH548WQApg6toGFYZdS2JZ9vyEWWlFKq20g7EIjI\nV0Rkg4isE5G7bOk3iEijte1cW/pcK61RRK5P9/2T8fET69h85/n85V9mkueYVzB73MCuyIJSSnVb\naQ0fFZEzgfnAJGPMMREZYKWPBxYAE4DBwJMiMsZ62c+As4GtwEoRWW6MWZ9OPpRSSnVeuvMIrgLu\nNMYcAzDG7LLS5wNLrfRNItIITLO2NRpjNgKIyFJr35wGgts+MoETHU1GSinlF+k2DY0BThWRF0Xk\nWRE5yUqvBbbY9ttqpXmlxxCRhSKySkRW7d69O81sxnfZKcOZWNs3q++hlFLdVcIagYg8CQxy2XSj\n9fpKYAZwEvCAiIwA1zvEG9wDj+swHmPMYmAxQENDgw71UUqpLEkYCIwxc7y2ichVwF9MaLruSyLS\nDlQRutIfYtu1DthuPfZKV0oplQPpNg39FZgNYHUGFwB7gOXAAhEpFJF6YDTwErASGC0i9SJSQKhD\neXmaeVBKKZWGdDuLlwBLRGQt0AxcZtUO1onIA4Q6gVuBRcaYNgARuRpYAQSBJcaYdWnmQSmlVBqk\nJyzC1tDQYFatWpXrbCilVI8iIquNMQlnzfpiZrFSSilvGgiUUsrnNBAopZTP9Yg+AhHZDbybxiGq\nCI1mUnounPR8RNPz0aE3nIthxpjqRDv1iECQLhFZlUyHiR/ouYim5yOano8OfjoX2jSklFI+p4FA\nKaV8zi+BYHGuM9CN6LmIpucjmp6PDr45F77oI1BKKeXNLzUCpZRSHnp1IMjFbTFzTUSGiMjTIvKG\ndfvQa630fiLyhIi8bf2utNJFRH5qnaM1IjI1t58g80QkKCKviMjD1vN66x4ab4vI/dYCiFiLJN5v\nnYsXRWR4LvOdDSJSISIPisib1nfkZL9+N0TkX62/kbUi8kcRKfLrd6PXBgIRCRK6LeZ5wHjgUusW\nmr1dK/BvxpjjCN0nYpH1ua8HnjLGjAaesp5D6PyMtn4WAr/o+ixn3bXAG7bn/w7cY52LfcAXrPQv\nAPuMMaOAe6z9epufAI8ZY8YBkwmdF999N0SkFrgGaDDGTCS0COYC/PrdMMb0yh/gZGCF7fkNwA25\nzlcOzsMyQveI3gDUWGk1wAbr8S+BS237R/brDT+E7nnxFKHl0h8mdNOkPUCe83tCaFXck63HedZ+\nkuvPkMFzUQ5scn4mP3436LhbYj/r//ph4Fy/fjd6bY2AFG6L2VtZ1dcTgBeBgcaYHQDW7wHWbr39\nPP0Y+AbQbj3vD+w3xrRaz+2fN3IurO0HrP17ixHAbuDXVlPZr0SkFB9+N4wx24AfAO8BOwj9X6/G\np9+N3hwIvG6X6Qsi0gf4M3CdMeZgvF1d0nrFeRKRC4BdxpjV9mSXXU0S23qDPGAq8AtjzAnAYTqa\ngdz02vNh9YPMB+qBwUApoaYwJ198N3pzIIh3u8xeTUTyCQWBe40xf7GSd4pIjbW9Bthlpffm8zQT\n+IiIbAaWEmoe+jFQISLhmzLZP2/kXFjb+wJ7uzLDWbYV2GqMedF6/iChwODH78YcYJMxZrcxpgX4\nC3AKPv1u9OZA4MvbYoqIAP8NvGGM+ZFt03LgMuvxZYT6DsLpn7NGiMwADoSbCXo6Y8wNxpg6Y8xw\nQv//fzfGfBp4GviEtZvzXITP0Ses/XvNVZ8x5n1gi4iMtZLOInQXQd99Nwg1Cc0QkRLrbyZ8Lnz5\n3ch5J0U2f4B5wFvAO8CNuc5PF33mWYSqrGuAV62feYTaM58C3rZ+97P2F0Kjq94BXic0iiLnnyML\n5+UM4GHr8QhC99BuBP4EFFrpRdbzRmv7iFznOwvnYQqwyvp+/BWo9Ot3A7gNeBNYC/weKPTrd0Nn\nFiullM/15qYhpZRSSdBAoJRSPqeBQCmlfE4DgVJK+ZwGAqWU8jkNBEop5XMaCJRSyuc0ECillM/9\nf9DA+hiS03yrAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f7cb30164a8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from IPython.display import clear_output\n",
    "\n",
    "rewards = []\n",
    "for i in range(1000):\n",
    "    rewards.append(play_and_train(env, agent))\n",
    "    agent.epsilon *= 0.99\n",
    "\n",
    "    if i % 100 == 0:\n",
    "        clear_output(True)\n",
    "        print('eps =', agent.epsilon, 'mean reward =', np.mean(rewards[-10:]))\n",
    "        plt.plot(rewards)\n",
    "        plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binarized state spaces\n",
    "\n",
    "Use agent to train efficiently on CartPole-v0.\n",
    "This environment has a continuous set of possible states, so you will have to group them into bins somehow.\n",
    "\n",
    "The simplest way is to use `round(x,n_digits)` (or numpy round) to round real number to a given amount of digits.\n",
    "\n",
    "The tricky part is to get the n_digits right for each state to train effectively.\n",
    "\n",
    "Note that you don't need to convert state to integers, but to __tuples__ of any kind of values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "env = gym.make(\"CartPole-v0\")\n",
    "n_actions = env.action_space.n\n",
    "\n",
    "print(\"first state:%s\" % (env.reset()))\n",
    "plt.imshow(env.render('rgb_array'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Play a few games\n",
    "\n",
    "We need to estimate observation distributions. To do so, we'll play a few games and record all states."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_states = []\n",
    "for _ in range(1000):\n",
    "    all_states.append(env.reset())\n",
    "    done = False\n",
    "    while not done:\n",
    "        s, r, done, _ = env.step(env.action_space.sample())\n",
    "        all_states.append(s)\n",
    "        if done:\n",
    "            break\n",
    "\n",
    "all_states = np.array(all_states)\n",
    "\n",
    "for obs_i in range(env.observation_space.shape[0]):\n",
    "    plt.hist(all_states[:, obs_i], bins=20)\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binarize environment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from gym.core import ObservationWrapper\n",
    "\n",
    "\n",
    "class Binarizer(ObservationWrapper):\n",
    "\n",
    "    def observation(self, state):\n",
    "\n",
    "        # state = <round state to some amount digits.>\n",
    "        # hint: you can do that with round(x,n_digits)\n",
    "        # you will need to pick a different n_digits for each dimension\n",
    "\n",
    "        return tuple(state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "env = Binarizer(gym.make(\"CartPole-v0\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_states = []\n",
    "for _ in range(1000):\n",
    "    all_states.append(env.reset())\n",
    "    done = False\n",
    "    while not done:\n",
    "        s, r, done, _ = env.step(env.action_space.sample())\n",
    "        all_states.append(s)\n",
    "        if done:\n",
    "            break\n",
    "\n",
    "all_states = np.array(all_states)\n",
    "\n",
    "for obs_i in range(env.observation_space.shape[0]):\n",
    "\n",
    "    plt.hist(all_states[:, obs_i], bins=20)\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Learn binarized policy\n",
    "\n",
    "Now let's train a policy that uses binarized state space.\n",
    "\n",
    "__Tips:__ \n",
    "* If your binarization is too coarse, your agent may fail to find optimal policy. In that case, change binarization. \n",
    "* If your binarization is too fine-grained, your agent will take much longer than 1000 steps to converge. You can either increase number of iterations and decrease epsilon decay or change binarization.\n",
    "* Having 10^3 ~ 10^4 distinct states is recommended (`len(QLearningAgent._qvalues)`), but not required.\n",
    "* A reasonable agent should get to an average reward of >=50."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "agent = QLearningAgent(alpha=0.5, epsilon=0.25, discount=0.99,\n",
    "                       get_legal_actions=lambda s: range(n_actions))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rewards = []\n",
    "for i in range(1000):\n",
    "    rewards.append(play_and_train(env, agent))\n",
    "\n",
    "    # OPTIONAL YOUR CODE: adjust epsilon\n",
    "    if i % 100 == 0:\n",
    "        clear_output(True)\n",
    "        print('eps =', agent.epsilon, 'mean reward =', np.mean(rewards[-10:]))\n",
    "        plt.plot(rewards)\n",
    "        plt.show()"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
